import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author tmh
 * @date 2024/10/8 16:47
 * @description
 */
public class T215数组中的第K个最大元素 {
    public int findKthLargest(int[] nums, int k) {
        //把数组里面的元素放在集合里面
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        return quickFind(list,k);

    }

    private int quickFind(List<Integer> list, int k) {
        Random random = new Random();
        //这里是需要从集合里面获得元素的
        int pivot = list.get(random.nextInt(list.size()));
        List<Integer> big = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        List<Integer> small = new ArrayList<>();
        for (Integer num : list) {
            if (num > pivot) {
                big.add(num);
            } else if (num == pivot) {
                equal.add(num);
            } else {
                small.add(num);
            }
        }
        if (k <= big.size()) {
            return quickFind(big, k);
        }
        //满足这个条件我们才可以去small集合里面查找元素
        if (list.size() - small.size() < k) {
            return quickFind(small, k - list.size() + small.size());
        }
        return pivot;
    }
}
